package com.hao.recursion;

import java.util.Arrays;

/**
 * TODO
 * 解决八皇后问题
 * @author 97472
 * @version 1.0
 * @date 2021/5/6 16:20
 */
public class Queue8 {
    /**
     *   使用一个一位数组代表棋盘，我们将数组的index表示行数，checkerboard[index]表示列数。
     *   由于我们要解决的是8皇后问题所所以我们固定了数组的大小
     */
    private Integer[] checkerboard = new Integer[8];
    /**
      *  最大行，和最大列的值
      */
    private Integer maxNum = 8;

    /**
      *  解法的统计
      */
    private Integer count = 0;


    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.solve();
        System.out.print("共有"+ queue8.count+"种解法");
    }

    public void solve(){
        check(0);
    }
    public void check(int n){
        // 判断是否已经到了完成了最后一行
        if (n == maxNum){
            count++;
            System.out.println(toString());
            return;
        }
        for (int i = 0; i < maxNum; i++) {
            checkerboard[n] = i;
            if (judge(n)){
                check(n+1);
            }
        }
    }
    // 判断第n行的皇后是否合法
    public Boolean judge(int n){
        for (int i = 0; i < n; i++) {
            // checkerboard[i] == checkerboard[n] 表示的是该行是否与第i行是否是同一列
            // Math.abs(n -i) == Math.abs(checkerboard[n] - checkerboard[i]) 表示的是该行是否与i行是否再同一斜线上
            if (checkerboard[i] == checkerboard[n] ||Math.abs(n -i) == Math.abs(checkerboard[n] - checkerboard[i])){
                return false;
            }
        }
        return true;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < checkerboard.length; i++) {
            res.append(" " + checkerboard[i]);
        }
        return res.toString();
    }
    public Integer getCount() {
        return count;
    }
}
